class Solution(object):
    def matrixReshape(self, mat, r, c):
        """
        :type mat: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        m = len(mat)
        n = len(mat[0])
        if m * n != r * c:
            return mat
        new_matrix = [0] * m * n
        out_matrix = [[0 for _ in range(c)] for _ in range(r)]
        index = 0
        for i in range(m):
            for j in range(n):
                new_matrix[index] = mat[i][j]
                index += 1
        index = 0
        for i in range(r):
            for j in range(c):
                out_matrix[i][j] = new_matrix[index]
                index += 1
        return out_matrix


